
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1689. -- [Usaco2005 Open] Muddy roads -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1689: [Usaco2005 Open] Muddy roads</h2><span class=green>Time Limit: </span>5 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>86&nbsp;&nbsp;<span class=green>Solved: </span>64<br>[<a href='submitpage.php?id=1689'>Submit</a>][<a href='problemstatus.php?id=1689'>Status</a>][<a href='bbs.php?id=1689'>Discuss</a>]</center><h2>Description</h2><div class=content>Farmer John has a problem: the dirt road from his farm to town has
suffered in the recent rainstorms and now contains (1 <= N <= 10,000)
mud pools.

Farmer John has a collection of wooden planks of length L that he
can use to bridge these mud pools. He can overlap planks and the
ends do not need to be anchored on the ground. However, he must
cover each pool completely.

Given the mud pools, help FJ figure out the minimum number of planks
he needs in order to completely cover all the mud pools.

</div><h2>Input</h2><div class=content>* Line 1: Two space-separated integers: N and L

* Lines 2..N+1: Line i+1 contains two space-separated integers: s_i
        and e_i (0 <= s_i < e_i <= 1,000,000,000) that specify the
        start and end points of a mud pool along the road. The mud
        pools will not overlap.  These numbers specify points, so a
        mud pool from 35 to 39 can be covered by a single board of
        length 4. Mud pools at (3,6) and (6,9) are not considered to
        overlap.

有N个MUD,用长度为L的木块去Cover.问至少要多少块.</div><h2>Output</h2><div class=content>* Line 1: The miminum number of planks FJ needs to use.

</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>3 3<br />
1 6<br />
13 17<br />
8 12<br />
<br />
INPUT DETAILS:<br />
<br />
FJ needs to use planks of length 3 to cover 3 mud pools.  The mud pools<br />
cover regions 1 to 6, 8 to 12, and 13 to 17.<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>5<br />
<br />
OUTPUT DETAILS:<br />
<br />
FJ can cover the mud pools with five planks of length 3 in the<br />
following way:<br />
                   111222..333444555....<br />
                   .MMMMM..MMMM.MMMM....<br />
                   012345678901234567890</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Silver'>Silver</a></p></div><center>[<a href='submitpage.php?id=1689'>Submit</a>][<a href='problemstatus.php?id=1689'>Status</a>][<a href='bbs.php?id=1689'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
